package leetbook.stack;

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * 基本计算器
 * 通用思路：先转后缀再计算
 */

public class Solution227 {

    public static void main(String[] args) {
        String s = "1+((2+3)*4)-5";
        System.out.println(new Solution227().calculate(s));
    }

    public int calculate(String s) {
        return calculPost(midToPost(s));
    }

    /**
     * 中缀表达式转后缀
     * @param s
     * @return
     */
    public Queue<String> midToPost(String s){
        Stack<String> ops = new Stack<>();  //存储操作符号和括号
        Queue<String> post = new LinkedList<>(); //存储后缀表达式
        HashMap<String,Integer> prior = new HashMap<>();
        prior.put("(",0);
        prior.put("+",1);prior.put("-",1);
        prior.put("*",2);prior.put("/",2);
        int i = 0;
        while (i<s.length()){
            //空格
            if(s.charAt(i)==' '){
                i++;
                continue;
            }
            //数字
            if(Character.isDigit(s.charAt(i))){
                int tmp = i; //如果是数字，记录数字起始位置
                while(i<s.length()&&Character.isDigit(s.charAt(i))) i++;
                post.offer(s.substring(tmp,i));
                continue;
            }
            //运算符
            if(ops.isEmpty()||s.charAt(i)=='('){  //ops空或者左括号直接压栈
                ops.push(s.charAt(i)+"");
            }else if(s.charAt(i)==')'){ //右括号需要把左括号后面的操作符号全部出栈
                String tmp = null;
                while (!(tmp=ops.pop()).equals("(")) post.offer(tmp);
            }else {                     //栈不空且四则运算，需要把比当前运算符级别高的运算符出栈
                String cur = s.charAt(i)+"";
                int pri = prior.get(cur);
                while (!ops.isEmpty()&&prior.get(ops.peek())>=pri){
                    post.offer(ops.pop());
                }
                ops.push(cur);         //当前操作符号入栈
            }
            i++;
        }
        //把栈里剩余的操作符加入后缀
        while (!ops.isEmpty()) post.offer(ops.pop());
        return post;
    }

    /**
     * 后缀表达式求值
     * @return
     */
    public int calculPost(Queue<String> post){
        Stack<Integer> stack = new Stack<>();
        for (String s: post) {
            if("+".equals(s)){
                stack.push(stack.pop()+stack.pop());
            }else if("-".equals(s)){
                stack.push(-stack.pop()+stack.pop());
            }else if("*".equals(s)){
                stack.push(stack.pop()*stack.pop());
            }else if("/".equals(s)){
                stack.push((int)(1.0/stack.pop()*stack.pop()));
            }else{
                stack.push(Integer.parseInt(s));
            }
        }
        return stack.pop();
    }



}
